package top.datacluster.basic.structure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Huffman {

    private Node root;

    public Huffman(Node[] src){
        List<Node> list = new ArrayList<>();
        for (Node n : src){
            list.add(n);
        }
        Node node = null;

        while (list.size() > 1){
            Collections.sort(list);

            Node left = list.get(0);
            Node right = list.get(1);
            node = new Node(left.getWeight() + right.getWeight());
            node.setLeft(left);
            node.setRight(right);
            list.add(node);
            list.remove(0);
            list.remove(0);
        }
        root = node;

    }

    public void print(){
//        for (Node n : data){
//            if (n != null){
//                System.out.print(n.getWeight() + " ");
//            }
//        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node[] src = new Node[5];
        src[0] = new Node(7);
        src[1] = new Node(10);
        src[2] = new Node(5);
        src[3] = new Node(21);
        src[4] = new Node(19);
        Huffman huffman = new Huffman(src);
        huffman.print();
    }



    public static class Node implements Comparable<Node>{

        private int weight;

        private Node left;

        private Node right;

        public Node(int weight) {
            this.weight = weight;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.getWeight());
        }
    }
}
